// link.c
// 头插法实现单链表
#include <stdio.h>
#include <stdlib.h>
// 节点
//存储密度 4/12 = 
//顺序表 > 单链表 > 双链表 > 哈希表（散列表）
// 哈希表（散列表）存储密度比较小，存储因子 70%
typedef struct Node
{
    int data;               //数据域
    struct Node *next;      //指针域，当前节点的后继元素
}Node;
// 操作
void add(Node *header,int e);
void show(Node *header);
void insert(Node *header,int index, int e);
void del(Node *header,int index);
Node *get(Node *header,int index);
int len(Node *header);

int size = 0;
int main()
{
    // 头指针
    Node *header;
    header = malloc(sizeof(Node));

    // 空表
    header->next = NULL;

    add(header,100);
    add(header,200);
    add(header,300);
    add(header,400);
    show(header);
    printf("大小：%d\n",len(header));
    insert(header,2,666);
    add(header,500);
    show(header);
    del(header,0);
    show(header);
    Node* a = get(header ,1);
    printf("%d\n",a->data);
    

    return 0;
}
//头插法 创建新的节点，将新节点一直插入到头的位置
// O(1) 
void add(Node *header,int e)
{
    //创建一个节点
    Node *node;
    node = malloc(sizeof(node));
    node->data = e;

    // 头指针的后继赋给新节点的后继，新节点指向头节点的后继节点，没有数据元素也对
    node ->next = header ->next;
    //让头指针指向新节点
    header->next = node;

    size++;
}

void show(Node *header)
{
    printf("-------------");
    
    printf("\n");
    printf("链表：");
    Node *n = header->next;
    while(n != NULL)
    {
        printf("%d ",n->data);
        // 获得后继节点
        n = n->next;
    }
    printf("\n");
}
void insert(Node *header,int index, int e)
{

    int l = len(header);
    //索引节点
    Node *a = header;
    //5
    //4 3 2 1 0
    for(int i = 0;i < l - index;i++)
    {
        a = a->next;
    }
    //创建一个节点
    Node *node;
    node = malloc(sizeof(node));
    node->data = e;
    // 新节点指向目标节点的后继
    node->next = a->next;
    //目标节点指向新节点
    a->next = node;

}

void del(Node *header,int index)
{
    int l = len(header);
    Node *a = header;
    //找到前一个
    for(int i =1 ;i<l-index;i++)
    {
        a=a->next;
    }
    a->next = a->next->next;
    free(a->next);
    a->next = NULL;
}

int len(Node *header)
{
    int len = 0;
    Node *n = header->next;
    while(n != NULL)
    {
        len++;
        // 获得后继节点
        n = n->next;
    }
    return len;
}

Node *get(Node *header,int index)
{
    int l = len(header);
    Node *a = header;
    //找到前一个
    for(int i =1 ;i<=l-index;i++)
    {
        a=a->next;
    }
    return a;
}